package com.cskaoyan.day01.linkdemo;

/**
 * 找到环起始点
 * @author stone
 * @date 2022/01/27 14:37
 */
public class LinkedDemo4 {

    public static void main(String[] args) {
        Node node1 = new Node("红");
        Node node2 = new Node("橙");
        Node node3 = new Node("黄");
        Node node4 = new Node("绿");
        Node node5 = new Node("青");
        Node node6 = new Node("蓝");
        Node node7 = new Node("紫");

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;

        node7.next = node5;//指向的是谁，环起始点就是谁

        Node startNode = getStartNode(node1);
        System.out.println("环起始位置：" + startNode.value);
    }

    private static Node getStartNode(Node head) {
        if (!LinkedDemo3.hasCircle(head)) {
            throw new RuntimeException("不成环");
        }
        //定义快慢结点
        Node fast = head;
        Node slow = head;
        //制造相遇
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                //成环
                break;
            }
        }
        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;//return fast;也可以
    }
}
